package com.shuo.dsa.niuke;

/**
 * 统计一个数字在排序数组中出现的次数
 * 思路: 二分法找出k对应的index, 然后前扫再后扫
 */
public class GetNumberOfK {
    public int GetNumberOfK(int[] array, int k) {
        if (array.length == 0) return 0;
        int lo = 0;
        int hi = array.length - 1;
        int mid = (lo + hi) / 2;
        boolean isFind = false;
        while (lo <= hi) {
            if (k > array[mid]) {
                lo = mid;
                mid = (lo + hi) / 2;
            } else if (k > array[mid]) {
                hi = mid;
                mid = (lo + hi) / 2;
            } else {
                isFind = true;
                break;
            }
        }
        if (!isFind) return 0;
        int count = -1;
        int index = mid;
        while ((index >= 0) && array[index] == k) {
            count++;
            index--;
        }
        index = mid;
        while ((index <= array.length - 1) && array[index] == k) {
            count++;
            index++;
        }
        return count;
    }

    public static void main(String[] args) {
        new GetNumberOfK().GetNumberOfK(new int[]{3, 3, 3, 3, 4, 5}, 3);
    }
}
